package algorithm.search;

import java.util.Arrays;

//斐波那契查找
public class FibonacciSearch {
   static int sizeMax = 20;
    public static void main(String[] args) {
//        int[] nums = new int[8];
//        for (int i =1;i<=8;i++){
//            nums[i-1] = fib2(i);
//        }
//        System.out.println(Arrays.toString(nums));
        int [] arr = {1,8, 10, 89, 1000, 1234};
        System.out.println(fibSearch(arr, 1000));


    }
    public static int fibSearch(int[] a, int key) {
            int low = 0;
            int high = a.length-1;
            int[] f = fib();
            int k = 0;//用来控制斐波那契数列
            int mid = 0;
        int[] temp = null;
        //获取到斐波那契分割数值的下标
        while (high>f[k]-1){
          k++;
        }
        if (f[k]>a.length){
          temp  = Arrays.copyOf(a, f[k]);
        }
        for (int i = a.length;i<f[k];i++){
            temp[i] = a[a.length-1];
        }

        while (low<=high){
            mid = low +f[k-1]-1;
            if (key<a[mid]){
                high = mid-1;
                k--;
            }else if (k>a[mid]){
                low = mid+1;
                k++;
            }else {
                return Math.min(mid, high);
            }
        }
        return -1;
    }

    //构建斐波那契数列---非递归版
    public static int[] fib(){
        int[] nums = new int[sizeMax];
        nums[0]=1;
        nums[1]=1;
        for (int i=2;i<nums.length;i++){
            nums[i] = nums[i-2]+nums[i-1];
        }
        return nums;
    }





    //递归版
    public static int fib2(int n ){
        if (n==1||n==2){
            return 1;
        }
        return fib2(n-1)+fib2(n-2);

    }
}
